In order to display interlaced video signals on a progressive or sequential line display with high visual quality, it is necessary to `deinterlace` interlaced odd and even fields of video signals into a sequentially continuous field of pixels without (interline) gaps. In addition, deinterlacing, prior to printing, results in higher quality still pictures from video.
In an interlaced video frame, each frame of pixels is composed of two time sequential fields--an even field and an odd field. Compared to a full frame of successive lines without missing lines of pixels, each (odd or even) field is subsampled by a factor of two in the vertical dimension, so that, as diagrammatically illustrated in FIG. 1, an even field contains data at only even-numbered line locations (e.g. lines 0, 2, 4, 6, and 8), and an odd field contains data at only odd-numbered line locations (e.g. lines 1, 3, 5, 7,). Thus, an even field has no pixel values for odd numbered lines of the full frame, and an odd field has no pixel values for even numbered line of the full frame.
In order to deinterlace an even (or an odd) field into a full frame without missing lines of pixels, it is necessary to estimate the missing odd (or even) lines. One well-known method for this purpose involves merging the even and odd fields together, namely simply filling in the missing lines of the odd (even) field with the lines of the immediately adjacent even (odd) field. Unfortunately, such an approach introduces "jitter" artifacts at portions of the image containing moving objects (i.e. objects that move within the time interval of two successive fields). 0n the other hand, merging provides optimal spatial resolution at steady image regions (namely at those pixel locations where the image does not change between successive fields).
Another approach is to concentrate on a single field only (i.e., the odd field) and interpolate the missing lines using spatial interpolation. One example of a relatively simple spatial interpolation technique involves bilinear interpolation, in which an average of the available pixel values in lines immediately above and below the pixel of interest in the missing line is assigned to the missing pixel. However, this method may cause artifacts if the missing pixel is over an edge whose orientation is not vertical.
To overcome these artifacts, an edge-adaptive spatial interpolation method, described in the U.S. Patent to Dougall et al., U.S. Pat. No. 5,019,903, entitled "Spatial Interpolation Between Lines Of A Supersampled Digital Video Signal In Accordance With A Gradient Vector Selected For Maximum Matching Of Blocks 0f Samples Which Are Offset In Opposite Directions," has been proposed. The patented technique first attempts to determine the orientation of the image gradient at the missing pixel, and then interpolation is performed using image values that are located along this determined orientation, in order not to "cross an edge" and cause unwanted artifacts.
The Dougall et al. patent proposes that a potentially more effective method would be to use a hybrid scheme, where the deinterlacing process would switch, on a pixel-by-pixel basis, between merging and (edge-adaptive) spatial interpolation, depending on the dynamics of the image at the locations of the missing pixels, so that the reduced complexity advantages of using merging in steady regions of the image would be maintained.
In order to classify the dynamics of each pixel as either a "moving pixel" or "steady pixel," it would be necessary to employ a motion detection scheme as a precursor to choosing merging or interpolation. However, the Dougall et al patent offers no discussion as to how to implement such a mechanism.
In order to detect motion in an image, the contents of successive image fields of opposite polarity (even-odd or odd-even) can be compared with one another. However, the accuracy of motion detection can be increased significantly when two consecutive fields of the same polarity (i.e., an immediately preceding even (odd) field (i-1) and an immediately succeeding even (odd) field (i+1)), between which an odd (even) field (i) occurs, are utilized for motion detection.
The U.S. patent to Bennett et al., U.S. Pat. No. 4,472,732 describes a method which employs the pixel-to-pixel difference of neighboring fields with the same polarity (e.g. even fields) that immediately follow and precede the field to be deinterlaced (e.g. an odd field), in order to perform motion detection. The method then switches between merging and vertical interpolation depending upon the presence and absence of motion that is determined by thresholding the difference values.
Unfortunately, the use of single-pixel differences may falsely detect `no motion` if the scene is such that the gray levels of the pixels being compared in the two neighboring fields are similar, even though there is motion in the scene. Such a situation may occur, for instance, in the case of scenes that contain a moving structure with text on it.
An example of this circumstance is illustrated in FIG. 2, which diagrammatically depicts what is essentially a black letter `E` rotated clockwise by 90.degree. and situated against a white background. For this illustrated image, a `no motion` decision is rendered at the (missing) pixel location (x,y) in the field at time t2, by differencing co-located values at fields at times t1 and t3, although there is motion at that pixel location. In this case, merging the fields am times t1 and t2 at pixel location (x,y) will result in artifacts due to this false classification.
The occurrence of such false classifications may be reduced by differencing and thresholding an N1.times.N2 block of pixels (e.g. N1=N2=3) rather than a single pixel. The benefits of using a 1.times.2 block (i.e. N1=1, N2=2), for instance, and thresholding the difference (1/2)(.vertline.f(x,y, t1)-f(x,y, t3).vertline.+.vertline.f(x+1,y, t1) -f(x+1,y, t3).vertline.) to detect whether or not the missing pixel f(x,y, t2) belongs to a moving region may be seen in FIG. 3, where f(.,.,.) denotes the spatiotemporal distribution of the fields.
If, as shown at time t4 in FIG. 4, a further fourth field is used for motion detection, a comparison of the fields at times t2 and t4 (in addition to the comparison of the fields at times t1 and t3) may increase the reliability of motion detection. In the example of FIG. 4, a "moving" decision can be rendered for the pixel of interest in the frame at time t2 as a result of comparing the corresponding pixels (at spatial location (x,y+1)) at frames at times t2 and t4.
The U.S. patent to Ishikawa, U.S. Pat. No. 4,785,351 describes a deinterlacing scheme, as applied to a time sequence of interlaced fields, such as an interlaced TV video signal, where motion detection is based not only upon the pixel-to-pixel difference of immediate neighbors (e.g. fields at t2 and t4, shown in FIG. 5), but also on the basis of a motion detection signal that has been obtained previously for deinterlacing t2, using t1 and t3, so as to effectively employ four consecutive fields.
In the scheme detailed in the '351 patent, in an effort to reduce noise, an average of existing pixel values of the fields surrounding the field of interest is placed in the location of the missing pixel, rather than directly using the value of a neighboring pixel (e.g. merging). However, since the existing lines in the field of interest that are directly reproduced in the deinterlaced version of the image are not processed for noise reduction, the averaging process for missing pixels may introduce some undesirable artifacts in the resulting image frame. Although such artifacts may not be visible in TV viewing applications, where the resulting frames are displayed in motion, they may be objectionable when the resulting deinterlaced frames are reproduced as still images (for display or printing). For example, over a stationary region, the missing lines that are generated by temporal. interpolation may appear less noisy than the adjacent unprocessed (existing) field lines, causing a visually disturbing effect, especially noticeable in printing applications.
The effect of the deinterlacing scheme described in the '351 patent is illustrated in FIG. 5. The patented mechanism employs a rolling memory system that is a cascade of two field stores and a line buffer, and makes the resulting deinterlaced frame available, on a pixel-by-pixel basis, to a display system, for example, in the case of a television platform performing interlaced to progressive scan conversion. In FIG. 5, as the field data (E2) at time t3 becomes available, motion detection is performed by taking the difference between values (E1) and (E2) from fields at times t1 and t3, respectively, e.g. the absolute difference .vertline.a3-c3.vertline., and comparing the difference with a threshold in order to detect motion for missing pixel value denoted as X1.
The binary motion detection decision is reflected by appropriately setting the value of a motion detection signal me (e.g. me=1 if there is motion). Depending upon the value of me, vertical interpolation (e.g. X1 =(1/2)(b2+b3)) or temporal interpolation (e.g. X1 =(1/2)(a3+c3)) is performed to produce the values of the deinterlaced frame at time t2.
Next, when the field at time t3 is deinterlaced, the fields at times t2 and t4 are employed for motion detection, e.g., absolute difference .vertline.b3-d3.vertline. is compared with a threshold to produce a binary motion detection signal mo. The motion detection signal for the missing pixel X2 is defined by logically ORing me and mo, i.e., md =(me)V(mo). In other words, the previous motion detection signal is stored and used for the next frame. It should be noted that the system described in the '351 patent produces deinterlaced frames in a sequential manner. For example, in the case shown in FIG. 5, the Ishikawa system first produces a deinterlaced version of the odd field 01 and then a deinterlaced version of the even field E2.
Another four-field based motion detection approach is described in the U.S. patent to Motoe et al, U.S. Pat. No. 5,021,870, where the missing pixel of interest is set to a value that is equal to a linear combination of the result of temporal averaging of values belonging to the surrounding fields that have the same parity, and the result of vertical spatial interpolation performed using the existing pixel values of the field of interest. The motion detection signal determines the weights assigned to these two quantities in forming the linear combination. This method uses a rolling memory system formed of three pixel stores and supplies the values of the deinterlaced frame pixel by pixel to a display system. As in the above-referenced '351 patent, pixel-by-pixel differences are employed to generate a motion detection signal.